import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 17:02
 * @description 设 f[i][j]表示只能放前i个物品的情况下，容量为j的背包所能达到的最大价值
 * 转移方程：假设已经处理好前i-1个物品，那么对于第i个物品，有两种选择
 * 1. 取第i个物品放入背包，那么背包剩余容量会减少 wi，价值增加 vi，那么最大价值为 f[i-1][j-wi] + vi
 * 2. 不取第i个物品，那么总价值不变，容量也不变。 f[i][j] = f[i-1][j]。
 *
 * 所以，状态转移方程为 f[i][j] = max(f[i-1][j], f[i-1][j-wi] + vi)，由于对fi有影响的只有fi-1，那么可以去掉第一维
 * 变成：
 * f[j] = max(f[j],  f[j-wi] + vi)
 */
public class Solution {
    public static void main(String[] args) {

    }

    /**
     * n个物品，背包容量为 W
     */
    int n, W;
    /**
     * n个物品的重量wi, 价值 vi
     */
    int[] w, v;
    /**
     * 背包容量为 f[i]时的最大价值
     */
    int[] f;

    public void dp() {
        // 注意：所有数据都没有初始化，需要维护
        for (int i = 1; i <= n; i++) {
            for (int l = W; l >= w[i]; l--) {
                f[l] = Math.max(f[l], f[l - w[i]] + v[i]);
            }
        }
    }
}
